public class SplitBalancedAlgorithm {


    /**
     * 在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
     * <p>
     * 给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
     * <p>
     * 返回可以通过分割得到的平衡字符串的最大数量。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "RLRRLLRLRL"
     * 输出：4
     * 解释：s 可以分割为 "RL", "RRLL", "RL", "RL", 每个子字符串中都包含相同数量的 'L' 和 'R'。
     * 示例 2：
     * <p>
     * 输入：s = "RLLLLRRRLR"
     * 输出：3
     * 解释：s 可以分割为 "RL", "LLLRRR", "LR", 每个子字符串中都包含相同数量的 'L' 和 'R'。
     * 示例 3：
     * <p>
     * 输入：s = "LLLLRRRR"
     * 输出：1
     * 解释：s 只能保持原样 "LLLLRRRR".
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= s.length <= 1000
     * s[i] = 'L' 或 'R'
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {
        SplitBalancedAlgorithm gemAlgorithm = new SplitBalancedAlgorithm();
        int num = gemAlgorithm.balancedStringSplitBest("RLLLLRRRLR");
        System.out.println("输出:" + num);
    }

    /**
     * 第一步：for循环截取beginIndex开始到当前循环的i的位置，从而获取到当前截取的字符串substring
     * 第二步：判断字符串substring的长度，如果长度为单数，则直接跳过当前循环；如果长度为双数，则进行第三步
     * 第三步：for循环字符串substring，分别记录字符'L'和字符'R'的数量，如果数量相等，即当前字符串substring为平衡字符串
     *
     * <p>
     * 时间复杂度O(n^2)
     * 控件复杂度O（1）
     * <p>
     * 执行用时 : 	9 ms
     * 内存消耗 : 34.1 MB
     */
    public int balancedStringSplit(String s) {
        int num = 0;
        int beginIndex = 0;
        for (int i = 0; i <= s.length(); i++) {
            String substring = s.substring(beginIndex, i);
            if (substring.length() % 2 != 0) {
                continue;
            }
            int numL = 0;
            int numR = 0;
            for (int j = 0; j < substring.length(); j++) {
                if (substring.charAt(j) == 'L') {
                    numL++;
                }
                if (substring.charAt(j) == 'R') {
                    numR++;
                }
            }
            if (numL == numR && numL != 0) {
                num++;
                beginIndex = i;
            }
        }
        return num;
    }

    /**
     * 最优解--java贪心算法
     */
    public int balancedStringSplitBest(String s) {
        int num = 0;
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'L') {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                num++;
            }
        }

        return num;
    }

}
